package com.gitee.feizns.explore.data_structure.tree.bs.easy;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author feizns
 * @since 2019/12/9
 */
public class PostOrderTraversal {

    public static void main(String[] args) {
        postOrderTraversal(create()).forEach(System.out::println);
    }

    public static List<Integer> postOrderTraversal(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        if ( root != null )
            stack.push(root);
        Stack<TreeNode> tmpStack = new Stack();
        while ( !stack.isEmpty() ) {
            TreeNode node = stack.pop();
            tmpStack.push(node);
            if ( node.left != null )
                stack.push(node.left);
            if ( node.right != null )
                stack.push(node.right);
        }
        while ( !tmpStack.isEmpty() ) {
            ret.add(tmpStack.pop().val);
        }
        return ret;
    }

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.right = new TreeNode(2);
        ret.right.left = new TreeNode(3);
        return ret;
    }

//    public static List<Integer> postOrderTraversal(TreeNode root) {
//        return postOrderTraversal(root);
//    }
//
//    private static List<Integer> postOrderTraversal(List<Integer> list, TreeNode root) {
//        if ( root != null ) {
//            postOrderTraversal(list, root.left);
//            postOrderTraversal(list, root.right);
//            list.add(root.val);
//        }
//        return list;
//    }

}
